import java.util.ArrayList;
import java.util.List;

/**
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * <p>
 * <p>
 * 上图为 8 皇后问题的一种解法。
 * <p>
 * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
 * <p>
 * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：4
 * 输出：[
 * [".Q..",  // 解法 1
 * "...Q",
 * "Q...",
 * "..Q."],
 * <p>
 * ["..Q.",  // 解法 2
 * "Q...",
 * "...Q",
 * ".Q.."]
 * ]
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<String>> res = solution.solveNQueens(4);
        System.out.println(res.size());
    }

    /**
     * 很典型需要用回溯来处理变量可能性
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[][] table = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            // 放置
            table[0][i] = true;
            loop(i, 0, table, result);
            // 回溯
            table[0][i] = false;
        }
        return result;
    }

    /**
     * x,y的位置已经被放置，开始递归，只考虑下一层
     *
     * @param x
     * @param y
     * @param table
     * @param result
     * @return
     */
    public void loop(int x, int y, boolean[][] table, List<List<String>> result) {
        if (y == table.length - 1) {
            // 如果已经处理完毕，则处理为最后的结果
            handle(table, result);
        }
        for (int i = 0; i < table.length; i++) {
            if (ok(i, y + 1, table)) {
                // 放置
                table[y + 1][i] = true;
                loop(i, y + 1, table, result);
                // 回溯
                table[y + 1][i] = false;
            }
        }
    }

    /**
     * 判断此次防止是否合法
     *
     * @param x
     * @param y
     * @param table
     * @return
     */
    public boolean ok(int x, int y, boolean[][] table) {
        // 竖向遍历
        for (int i = 0; i < y; i++) {
            if (table[i][x]) {
                return false;
            }
        }
        // 左斜下遍历
        for (int i = x + 1, j = y + 1; i < table.length && j < table.length; i++, j++) {
            if (table[j][i]) {
                return false;
            }
        }
        // 左斜上遍历
        for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
            if (table[j][i]) {
                return false;
            }
        }
        // 右斜上遍历
        for (int i = x + 1, j = y - 1; i < table.length && j >= 0; i++, j--) {
            if (table[j][i]) {
                return false;
            }
        }
        // 右斜下遍历
        for (int i = x - 1, j = y + 1; i >= 0 && j < table.length; i--, j++) {
            if (table[j][i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 处理为最后的结果
     *
     * @param table
     * @param result
     * @return
     */
    public void handle(boolean[][] table, List<List<String>> result) {
        List<String> one = new ArrayList<>();
        StringBuilder sb;
        for (int i = 0; i < table.length; i++) {
            sb = new StringBuilder();
            for (int j = 0; j < table.length; j++) {
                if (table[i][j]) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            one.add(sb.toString());
        }
        result.add(one);
    }

}